import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Map<String, Boolean> hash = new HashMap<>(); // 记录基因库中的序列
        Map<String, Boolean> visited = new HashMap<>(); // 记录已经访问过的序列
        for (String s : bank) {
            hash.put(s,true);
        }
        char[] changes = {'A','C','G','T'};
        // 判断 特殊情况
        if (startGene.equals(endGene)) {
            return 0;
        }
        if (!hash.containsKey(endGene)) { // 不存在库中
            return -1;
        }
        // 使用BFS遍历决策树
        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        visited.put(startGene, true);
        int ret = 0; // 记录走的步数
        while (!queue.isEmpty()) {
            ret++;
            int size = queue.size(); // 记录当前层的个数
            while (size-- != 0) {
                String s = queue.poll();
                // 字符串的每一位都发生了变化
                for (int i = 0; i < 8; i++) { // 字符串的长度为8
                    char[] tmp = s.toCharArray();
                    for (int j = 0; j < 4; j++) {
                        tmp[i] = changes[j]; // 将第i位的字符改为另外的字符
                        String next = new String(tmp);
                        // 判断next是否符合要求（存在bank库中 并且 未被访问）
                        if (hash.containsKey(next) && !visited.containsKey(next)) {
                            if (next.equals(endGene)) {
                                return ret;
                            }
                            queue.offer(next);
                            visited.put(next, true);
                        }
                    }
                }
            }
        }
        return -1;
    }
}